#include <vector>
#include <array>
#include <math.h>
#include <stdlib.h>
int __lg(int m) {
    if (m == 0)  return 0;
    int ret = 0;
    while (m != 1) {
        ++ret;
        m >>= 1;
    }
    return ret;
}
class Solution {
public:
    int findIntegers(int n) {
        int m = __lg(n);    // 最高位数
        std::vector<std::array<int, 2> > memo(m + 1, { -1,-1 });
        auto dfs = [&](auto&& dfs, int i, bool pre1, bool is_limit)-> int {
            if (i < 0) {
                // 已经遍历到尽头，返回的值相当于 数字为0的情况 ，
                return 1;
            }
            if (!is_limit && memo[i][pre1] >= 0)
            {
                // 算过
                return memo[i][pre1];
            }
            int up = is_limit ? n >> i & 1 : 1;         // 最高位
            int res = dfs(dfs, i - 1, false, is_limit && up == 0);
            if (!pre1 && up == 1) {
                res += dfs(dfs, i - 1, true, is_limit);
            }
            if (!is_limit) {
                memo[i][pre1] = res;
            }
            return res;
            };
        int mm = dfs(dfs, m, false, true);
        return mm;
    }
};
int main()
{
	cout << (3 & 3) <<' ';
    Solution().findIntegers(5);
	system("pause");
}